package cnki.kg.algorithm;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

public class MajorityElement {
    @Test
    public void  test(){
        int res2=majorityElement2(new int[]{3,4,3});
        System.out.println(res2);
    }
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> mp=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(mp.containsKey(nums[i])){
                mp.put(nums[i],mp.get(nums[i])+1);
            }else{
                mp.put(nums[i],1);
            }
        }
        for (Integer key : mp.keySet()) {
            if(mp.get(key)>nums.length/2){
                return key;
            }
        }
        return 0;
    }
    public int majorityElement2(int[] nums) {
        int count=1;
        int x=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(x==nums[i]){
                count++;
            }else{
                count--;
            }
            if(count==0){
                x=nums[i];
                count=1;
            }
        }

        return x;
    }
}
